{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check SubTree LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree #string-matching #hash-function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树 #字符串匹配 #哈希函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkSubTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查子树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。</p>\n",
    "\n",
    "<p>如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。</p>\n",
    "\n",
    "<p><strong>注意：</strong>此题相对书上原题略有改动。</p>\n",
    "\n",
    "<p><strong>示例1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：t1 = [1, 2, 3], t2 = [2]\n",
    "<strong> 输出</strong>：true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：t1 = [1, null, 2, 4], t2 = [3, 2]\n",
    "<strong> 输出</strong>：false\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>树的节点数目范围为[0, 20000]。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-subtree-lcci](https://leetcode.cn/problems/check-subtree-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-subtree-lcci](https://leetcode.cn/problems/check-subtree-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def isSame(tree1,tree2):\n",
    "            if not tree1 and not tree2:\n",
    "                return True\n",
    "            if not tree1 or not tree2:\n",
    "                return False\n",
    "\n",
    "            return tree1.val ==tree2.val and isSame(tree1.left,tree2.left) and isSame(tree1.right,tree2.right)\n",
    "        \n",
    "        if not t2:\n",
    "            return True\n",
    "        if not t1:\n",
    "            return False\n",
    "        \n",
    "        if t1.val !=t2.val:\n",
    "            return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "        elif isSame(t1.left,t2.left) and isSame(t1.right,t2.right):\n",
    "            return True\n",
    "        else:\n",
    "            return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def check_if_equal(self, t1:TreeNode, t2:TreeNode)->bool:\n",
    "        if t1 is None and t2 is None:\n",
    "            return True\n",
    "        elif t1 and t2:\n",
    "            if t1.val == t2.val:\n",
    "                return True\n",
    "        return False\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if t1 is None:\n",
    "            return False\n",
    "        if t1.val == t2.val and self.check_if_equal(t1.left, t2.left) and self.check_if_equal(t1.right, t2.right):\n",
    "            return True\n",
    "        left = self.checkSubTree(t1.left, t2)\n",
    "        right = self.checkSubTree(t1.right, t2)\n",
    "        if left or right:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t2 or not t1:return False\n",
    "        def dfs(t1,t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            elif not t1 or not t2:\n",
    "                return False\n",
    "            else:\n",
    "                if t1.val==t2.val:\n",
    "                    res = dfs(t1.left,t2.left) and dfs(t1.right,t2.right)\n",
    "                    if res:return True\n",
    "                return False\n",
    "        return dfs(t1,t2) or self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t2:\n",
    "            return True\n",
    "        if not t1:\n",
    "            return False\n",
    "        return self.helper(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "    \n",
    "    def helper(self, t1, t2):\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        return t1.val == t2.val and self.helper(t1.left, t2.left) and self.helper(t1.right, t2.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if t1==None:\n",
    "            return not t2\n",
    "        if t2==None:\n",
    "            return True\n",
    "        return self.dfs(t1,t2) or self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "    def dfs(self,t1,t2):\n",
    "        if t2==None and t1==None:\n",
    "            return True\n",
    "        elif t2==None or t1==None:\n",
    "            return False\n",
    "        elif t2.val!=t1.val:\n",
    "            return False\n",
    "        else:\n",
    "            return self.dfs(t1.left,t2.left) and self.dfs(t1.right,t2.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[1, 2, 3]\n",
    "[2]\n",
    "[1, null, 2, 4]\n",
    "[3, 2]\n",
    "\n",
    "The node numbers of both tree are in [0, 20000].\n",
    "\n",
    "Tree, Depth-First Search, Binary Tree, String Matching, Hash Function\n",
    "\"\"\"\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, main: TreeNode, sub: TreeNode) -> bool:\n",
    "        if not main: return not sub\n",
    "        return self.dfs(main, sub) or self.checkSubTree(main.left, sub) or self.checkSubTree(main.right, sub)\n",
    "    def dfs(self, main, sub):\n",
    "        if not main and not sub: return True\n",
    "        if not main or not sub: return False\n",
    "        return main.val == sub.val and self.dfs(main.left, sub.left) and self.dfs(main.right, sub.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def dfs(t1, t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            if not t1 or not t2:\n",
    "                return False\n",
    "            return t1.val==t2.val and dfs(t1.left, t2.left) and dfs(t1.right, t2.right)\n",
    "\n",
    "        #都为空？\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        if dfs(t1, t2):\n",
    "            return True\n",
    "        return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "\n",
    "#作者：MinghuiAn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1 and not t2 : return True\n",
    "        if not t1 or not t2 : return False\n",
    "        if t1.val == t2.val and self.check(t1, t2):\n",
    "            return True\n",
    "        return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "\n",
    "    def check(self, t1, t2):\n",
    "        if not t1 and not t2 : return True\n",
    "        if not t1 or not t2 : return False\n",
    "        if t1.val != t2.val: return False\n",
    "        return self.check(t1.left, t2.left) and self.check(t1.right, t2.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        if t1.val == t2.val:\n",
    "            return self.checkSubTree(t1.left, t2.left) and self.checkSubTree(t1.right, t2.right) \n",
    "        return self.checkSubTree(t1.right, t2) or self.checkSubTree(t1.left, t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def isSameTree(t1: TreeNode, t2: TreeNode) -> bool:\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            if not t1:\n",
    "                return False\n",
    "            if not t2:\n",
    "                return False\n",
    "            \n",
    "            return t1.val == t2.val and isSameTree(t1.left, t2.left) and isSameTree(t1.right, t2.right)\n",
    "        if not t2:\n",
    "            return True\n",
    "\n",
    "        if not t1 and t2:\n",
    "            return False\n",
    "        \n",
    "\n",
    "        if t1.val == t2.val:\n",
    "            if isSameTree(t1, t2):\n",
    "                return True\n",
    "\n",
    "        return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right, t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if self.is_same_tree(t1, t2):\n",
    "            return True\n",
    "        if t1.left is not None:\n",
    "            if self.checkSubTree(t1.left, t2):\n",
    "                return True\n",
    "        if t1.right is not None:\n",
    "            if self.checkSubTree(t1.right, t2):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def is_same_tree(\n",
    "        self,\n",
    "        root1: Optional[TreeNode],\n",
    "        root2: Optional[TreeNode],\n",
    "    ) -> bool:\n",
    "        if root1 is None and root2 is None:\n",
    "            return True\n",
    "        if root1 is None or root2 is None:\n",
    "            return False\n",
    "        if root1.val != root2.val:\n",
    "            return False\n",
    "        return self.is_same_tree(root1.left, root2.left) and self.is_same_tree(\n",
    "            root1.right, root2.right\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def dfs(t1,t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            if not t1 or not t2:\n",
    "                return False\n",
    "            return t1.val == t2.val and dfs(t1.left, t2.left) and dfs(t1.right, t2.right)\n",
    "        \n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        if dfs(t1,t2):\n",
    "            return True\n",
    "        \n",
    "        return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def dfs(t1, t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            if not t1 or not t2:\n",
    "                return False\n",
    "            return t1.val==t2.val and dfs(t1.left, t2.left) and dfs(t1.right, t2.right)\n",
    "\n",
    "        #都为空？\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        if dfs(t1, t2):\n",
    "            return True\n",
    "        return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if t1 is None and t2 is None:\n",
    "            return True\n",
    "        if t1 is None or t2 is None:\n",
    "            return False\n",
    "        def same(root1,root2):\n",
    "            if root1 is None and root2 is None:\n",
    "                return True\n",
    "            if root1 is None or root2 is None or root1.val!=root2.val:\n",
    "                return False\n",
    "            return same(root1.left,root2.left) and same(root1.right,root2.right)\n",
    "        \n",
    "        return same(t1,t2) or self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def isSame(tree1,tree2):\n",
    "            if not tree1 and not tree2:\n",
    "                return True\n",
    "            if not tree1 or not tree2:\n",
    "                return False\n",
    "\n",
    "            return tree1.val ==tree2.val and isSame(tree1.left,tree2.left) and isSame(tree1.right,tree2.right)\n",
    "        \n",
    "        if not t2:\n",
    "            return True\n",
    "        if not t1:\n",
    "            return False\n",
    "        \n",
    "        if t1.val !=t2.val:\n",
    "            return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "        elif isSame(t1.left,t2.left) and isSame(t1.right,t2.right):\n",
    "            return True\n",
    "        else:\n",
    "            return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "        \n",
    "# https://leetcode.cn/problems/check-subtree-lcci/solutions/375527/jian-cha-zi-shu-jin-100dai-ma-jian-ji-zhu-shi-xian/       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "\n",
    "        def dfs(t1, t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            if not t1 or not t2:\n",
    "                return False\n",
    "            if t1 and t2 and t1.val == t2.val:\n",
    "                return dfs(t1.left, t2.left) and dfs(t1.right, t2.right)\n",
    "            return False\n",
    "\n",
    "        if dfs(t1, t2):\n",
    "            return True\n",
    "        elif t1:\n",
    "            return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def dfs(self, node: TreeNode, tt: TreeNode) -> bool:\n",
    "        if tt is None and node is None:\n",
    "            return True\n",
    "        if node is None and tt is not None:\n",
    "            return False\n",
    "        if node is not None and tt is None:\n",
    "            return False\n",
    "        if node.val != tt.val :\n",
    "            return False\n",
    "        return self.dfs(node.left, tt.left) and self.dfs(node.right, tt.right)  \n",
    "\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if t1 is None:\n",
    "            return False\n",
    "        return self.dfs(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def dfs(t1, t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            if not t1 or not t2:\n",
    "                return False\n",
    "            return t1.val==t2.val and dfs(t1.left, t2.left) and dfs(t1.right, t2.right)\n",
    "\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        if dfs(t1, t2):\n",
    "            return True\n",
    "        return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def _tree_eq(self, t1, t2):\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "\n",
    "        val_eq = t1.val == t2.val\n",
    "        left_eq = self._tree_eq(t1.left, t2.left)\n",
    "        right_eq = self._tree_eq(t1.right, t2.right)\n",
    "\n",
    "        return val_eq and left_eq and right_eq\n",
    "    \n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "            \n",
    "        if not t1:\n",
    "            return False\n",
    "\n",
    "        if not t2:\n",
    "            return True\n",
    "\n",
    "        if self._tree_eq(t1, t2):\n",
    "            return True\n",
    "        \n",
    "        leq = self.checkSubTree(t1.left, t2)\n",
    "        req = self.checkSubTree(t1.right, t2)\n",
    "\n",
    "        return leq or req\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        root = []\n",
    "        self.findRoot(t1, t2, root)\n",
    "\n",
    "        if root:\n",
    "            for r in root:\n",
    "                flag = self.identicalTree(r, t2)\n",
    "                if flag == True:\n",
    "                    return True\n",
    "            return False \n",
    "        else:\n",
    "            return False \n",
    "\n",
    "    def findRoot(self, t1, t2, root: List) -> None:\n",
    "        if t1 is None:\n",
    "            return \n",
    "\n",
    "        if t1.val == t2.val:\n",
    "            root.append(t1)\n",
    "\n",
    "        self.findRoot(t1.left, t2, root)\n",
    "        self.findRoot(t1.right, t2, root)\n",
    "\n",
    "    def identicalTree(self, t1, t2) -> bool:\n",
    "        if t1 is None and t2:\n",
    "            return False\n",
    "        elif t2 is None and t1:\n",
    "            return False\n",
    "        elif t1 is None and t2 is None:\n",
    "            return True \n",
    "        \n",
    "        # print(t1, t2)\n",
    "        if t1.val != t2.val:\n",
    "            return False \n",
    "        else:\n",
    "            left_id = self.identicalTree(t1.left, t2.left)\n",
    "            right_id = self.identicalTree(t1.right, t2.right)\n",
    "            if left_id and right_id:\n",
    "                return True \n",
    "            else:\n",
    "                return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def is_valid(self, p, q):\n",
    "        if not p and not q:\n",
    "            return True\n",
    "        if not p or not q:\n",
    "            return False\n",
    "        print(p.val)\n",
    "        return p.val == q.val and self.is_valid(p.left, q.left) and self.is_valid(p.right, q.right)\n",
    "\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1:\n",
    "            return not t2\n",
    "        return self.is_valid(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def dfs(t1, t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            if not t1 or not t2:\n",
    "                return False\n",
    "            return t1.val == t2.val and dfs(t1.left, t2.left) and dfs(t1.right, t2.right)\n",
    "\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        if dfs(t1, t2):\n",
    "            return True\n",
    "        return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        root = []\n",
    "        self.findRoot(t1, t2, root)\n",
    "\n",
    "        if root:\n",
    "            for r in root:\n",
    "                flag = self.identicalTree(r, t2)\n",
    "                if flag == True:\n",
    "                    return True\n",
    "            return False \n",
    "        else:\n",
    "            return False \n",
    "\n",
    "    def findRoot(self, t1, t2, root: List) -> None:\n",
    "        if t1 is None:\n",
    "            return \n",
    "\n",
    "        if t1.val == t2.val:\n",
    "            root.append(t1)\n",
    "\n",
    "        self.findRoot(t1.left, t2, root)\n",
    "        self.findRoot(t1.right, t2, root)\n",
    "\n",
    "    def identicalTree(self, t1, t2) -> bool:\n",
    "        if t1 is None and t2:\n",
    "            return False\n",
    "        elif t2 is None and t1:\n",
    "            return False\n",
    "        elif t1 is None and t2 is None:\n",
    "            return True \n",
    "        \n",
    "        # print(t1, t2)\n",
    "        if t1.val != t2.val:\n",
    "            return False \n",
    "        else:\n",
    "            left_id = self.identicalTree(t1.left, t2.left)\n",
    "            right_id = self.identicalTree(t1.right, t2.right)\n",
    "            if left_id and right_id:\n",
    "                return True \n",
    "            else:\n",
    "                return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        \n",
    "        def isSameTree(ta: TreeNode, tb: TreeNode) -> bool:\n",
    "            if not ta and not tb:\n",
    "                return True\n",
    "            if not ta or not tb:\n",
    "                return False\n",
    "            return ta.val == tb.val and isSameTree(ta.left, tb.left) and isSameTree(ta.right, tb.right)\n",
    "        \n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "            \n",
    "        return isSameTree(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def is_valid(self, p, q):\n",
    "        if not p and not q:\n",
    "            return True\n",
    "        if not p or not q:\n",
    "            return False\n",
    "        return p.val == q.val and self.is_valid(p.left, q.left) and self.is_valid(p.right, q.right)\n",
    "\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1:\n",
    "            return not t2\n",
    "        return self.is_valid(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "\n",
    "# 作者：木子\n",
    "# 链接：https://leetcode.cn/problems/check-subtree-lcci/solutions/1141845/python-mian-shi-ti-0410-jian-cha-zi-shu-gxb6l/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def dfs(t1,t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            if not t1 or not t2:\n",
    "                return False\n",
    "            return t1.val == t2.val and dfs(t1.left, t2.left) and dfs(t1.right, t2.right)\n",
    "        \n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        if dfs(t1,t2):\n",
    "            return True\n",
    "        \n",
    "        return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1:\n",
    "            return False\n",
    "        if not t2:\n",
    "            return False\n",
    "        \n",
    "            \n",
    "        tequal = self.is_equal(t1, t2)\n",
    "        if tequal:\n",
    "            return True\n",
    "        \n",
    "        if self.checkSubTree(t1.left, t2):\n",
    "            return True\n",
    "        if self.checkSubTree(t1.right, t2):\n",
    "            return True\n",
    "        \n",
    "        return False\n",
    "    \n",
    "    def is_equal(self, t1, t2):\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1:\n",
    "            return False\n",
    "        if not t2:\n",
    "            return False\n",
    "        \n",
    "        return t1.val == t2.val and self.is_equal(t1.left, t2.left) and self.is_equal(t1.right, t2.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def dfs(t1,t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            if not t1 or not t2:\n",
    "                return False\n",
    "            return t1.val==t2.val and dfs(t1.left,t2.left) and dfs(t1.right,t2.right)\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        if dfs(t1,t2):\n",
    "            return True\n",
    "        return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1:\n",
    "            return False\n",
    "        if not t2:\n",
    "            return True\n",
    "        if self.dfs2(t1, t2):\n",
    "            return True\n",
    "        return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "\n",
    "\n",
    "    def dfs2(self, t1: TreeNode, t2: TreeNode):\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        return t1.val == t2.val and self.dfs2(t1.left, t2.left) and self.dfs2(t1.right, t2.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def process(self, head1, head2):\n",
    "        if head1.val != head2.val:\n",
    "            print(\"aaa\")\n",
    "            return False\n",
    "        elif head1.left and (not head2.left):\n",
    "            return False\n",
    "        elif head1.right and (not head2.right):\n",
    "            return False\n",
    "        elif (not head1.left) and head2.left:\n",
    "            return False\n",
    "        elif (not head1.right) and head2.right:\n",
    "            return False\n",
    "        \n",
    "        isl = True\n",
    "        isr = True\n",
    "        if head1.left:\n",
    "            print(head1.left.val, head2.left.val)\n",
    "            isl = self.process(head1.left, head2.left)\n",
    "        if head1.right:\n",
    "            isr = self.process(head1.right, head2.right)\n",
    "\n",
    "        return (isl and isr)\n",
    "\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        queue = []\n",
    "\n",
    "        queue.append(t1)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if not node:\n",
    "                continue\n",
    "            if node.val == t2.val:\n",
    "                res = self.process(node, t2)\n",
    "                if res:\n",
    "                    return True\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "\n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if None == t1 and None == t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        return self.isSame(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "        \n",
    "\n",
    "    \n",
    "    def isSame(self, t1: TreeNode, t2: TreeNode):\n",
    "        if None == t1 and None == t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False    \n",
    "        return t1.val == t2.val and self.isSame(t1.left, t2.left) and self.isSame(t1.right, t2.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        l2 = []\n",
    "        def parse2(root):\n",
    "            if root is None: return\n",
    "            parse2(root.left)\n",
    "            l2.append(root.val)\n",
    "            parse2(root.right)\n",
    "        parse2(t2)\n",
    "\n",
    "        self.flag = False\n",
    "\n",
    "        def parse(root):\n",
    "            if root is None: return []\n",
    "            left = parse(root.left)\n",
    "            if left == l2: self.flag = True\n",
    "            right = parse(root.right)\n",
    "            if right == l2: self.flag = True\n",
    "            return left + [root.val] + right\n",
    "\n",
    "        if parse(t1) == l2: self.flag = True\n",
    "\n",
    "        return self.flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def check(t1,t2,flag):\n",
    "    if t1 is None and t2 is None:\n",
    "        return True\n",
    "    elif t1 is None or t2 is None:\n",
    "        return False\n",
    "    if flag:\n",
    "        return check(t1.left,t2.left,1) and check(t1.right,t2.right,1)\n",
    "    else:\n",
    "        if t1.val==t2.val and check(t1.left,t2.left,1) and check(t1.right,t2.right,1):\n",
    "            return True\n",
    "        return check(t1.left,t2,0) or check(t1.right,t2,0)\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        return check(t1,t2,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def process(self, head1, head2):\n",
    "        if head1.val != head2.val:\n",
    "            print(\"aaa\")\n",
    "            return False\n",
    "        elif head1.left and (not head2.left):\n",
    "            return False\n",
    "        elif head1.right and (not head2.right):\n",
    "            return False\n",
    "        elif (not head1.left) and head2.left:\n",
    "            return False\n",
    "        elif (not head1.right) and head2.right:\n",
    "            return False\n",
    "        \n",
    "        isl = True\n",
    "        isr = True\n",
    "        if head1.left:\n",
    "            print(head1.left.val, head2.left.val)\n",
    "            isl = self.process(head1.left, head2.left)\n",
    "        if head1.right:\n",
    "            isr = self.process(head1.right, head2.right)\n",
    "\n",
    "        return (isl and isr)\n",
    "\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        queue = []\n",
    "\n",
    "        queue.append(t1)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if not node:\n",
    "                continue\n",
    "            if node.val == t2.val:\n",
    "                res = self.process(node, t2)\n",
    "                if res:\n",
    "                    return True\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "\n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if t1 == None:\n",
    "            return not t2\n",
    "        if t2 == None:\n",
    "            return True\n",
    "        # find the root of t2 in t1\n",
    "        return self.dfs(t1, t2) or self.checkSubTree(t1.left , t2) or self.checkSubTree(t1.right, t2)\n",
    "    \n",
    "    def dfs(self, t1, t2):\n",
    "        # t2 is over\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        # t2 is not over and t1 is over\n",
    "        elif not t1 or not t2:\n",
    "            return False\n",
    "        # not equal\n",
    "        elif t2.val != t1.val:\n",
    "            return False\n",
    "        # equal, then search left and right\n",
    "        else:\n",
    "            return self.dfs(t1.left, t2.left) and self.dfs(t1.right, t2.right)  # 注意这里是and\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t2:\n",
    "            return True\n",
    "\n",
    "        def isgood(root1, root2):\n",
    "            if not root1 and not root2:\n",
    "                return True\n",
    "            if not root1 or not root2:\n",
    "                return False\n",
    "            if root1.val != root2.val:\n",
    "                return False\n",
    "            ans = True\n",
    "            ans &= isgood(root1.left, root2.left)\n",
    "            ans &= isgood(root1.right, root2.right)\n",
    "            return ans\n",
    "        \n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return False\n",
    "            ans = False\n",
    "            if root.val == t2.val:\n",
    "                ans |= isgood(root, t2)\n",
    "            ans |= dfs(root.left)\n",
    "            ans |= dfs(root.right)\n",
    "            return ans\n",
    "        return dfs(t1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "#\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1:\n",
    "            return not t2\n",
    "        return self.check_sub_tree(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "\n",
    "    def check_sub_tree(self, root: TreeNode, check_root: TreeNode) -> bool:\n",
    "        if root is None and check_root is None:\n",
    "            return True\n",
    "        if root is None or check_root is None:\n",
    "            return False\n",
    "        else:\n",
    "            return root.val == check_root.val and self.check_sub_tree(root.left, check_root.left) and self.check_sub_tree(\n",
    "                root.right, check_root.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_valid(self, p, q):\n",
    "        if not p and not q:\n",
    "            return True\n",
    "        if not p or not q:\n",
    "            return False\n",
    "        return p.val == q.val and self.is_valid(p.left, q.left) and self.is_valid(p.right, q.right)\n",
    "\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1:\n",
    "            return not t2\n",
    "        return self.is_valid(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        def check(t1: TreeNode, t2: TreeNode):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            if not t1 or not t2 or t1.val != t2.val:\n",
    "                return False\n",
    "            return check(t1.left,t2.left) and check(t1.right,t2.right)\n",
    "        return check(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if t1==None:\n",
    "            return not t2\n",
    "        if t2==None:\n",
    "            return True\n",
    "        return self.dfs(t1,t2) or self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "    def dfs(self,t1,t2):\n",
    "        if t2==None and t1==None:\n",
    "            return True\n",
    "        elif t2==None or t1==None:\n",
    "            return False\n",
    "        elif t2.val!=t1.val:\n",
    "            return False\n",
    "        else:\n",
    "            return self.dfs(t1.left,t2.left) and self.dfs(t1.right,t2.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def dfs(node1,node2):\n",
    "            if not node1 and not node2:return True\n",
    "            if not node1 or not node2:return False\n",
    "            if node1.val != node2.val:return False\n",
    "            return dfs(node1.left,node2.left) and dfs(node1.right,node2.right)\n",
    "        if not t1:\n",
    "            return False\n",
    "        if dfs(t1,t2):\n",
    "            return True\n",
    "\n",
    "        return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "        \n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        \n",
    "        def count(head):\n",
    "            if not head:\n",
    "                return 0,0\n",
    "            l,lc = count(head.left)\n",
    "            r,rc = count(head.right)\n",
    "            return max(l,r)+1, lc+rc\n",
    "        tl, tc = count(t2)\n",
    "        \n",
    "        def check(a,b):\n",
    "            if not a and not b:\n",
    "                return True\n",
    "            if not a or not b:\n",
    "                return False\n",
    "            return a.val == b.val and check(a.left, b.left) and check(a.right, b.right)\n",
    "        \n",
    "        def dfs(head):\n",
    "            if not head:\n",
    "                return 0,0,False\n",
    "            l, lc, lok = dfs(head.left)\n",
    "            if lok:\n",
    "                return 0,0,True\n",
    "            r, rc, rok = dfs(head.right)\n",
    "            if rok:\n",
    "                return 0,0,True\n",
    "            lv, cnt = max(l,r)+1, lc+rc\n",
    "            if lv == tl and cnt == tc and head.val == t2.val and check(head,t2):\n",
    "                return 0,0,True\n",
    "            return lv,cnt,False\n",
    "        a,b,hit = dfs(t1)\n",
    "        return hit     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1:\n",
    "            return False\n",
    "        if not t2:\n",
    "            return True\n",
    "        return self.dfs2(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "\n",
    "    def dfs2(self, t1: TreeNode, t2: TreeNode):\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        return t1.val == t2.val and self.dfs2(t1.left, t2.left) and self.dfs2(t1.right, t2.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t2 or not t1:return False\n",
    "        def dfs(t1,t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            elif not t1 or not t2:\n",
    "                return False\n",
    "            else:\n",
    "                if t1.val==t2.val:\n",
    "                    res = dfs(t1.left,t2.left) and dfs(t1.right,t2.right)\n",
    "                    if res:return True\n",
    "                return False\n",
    "        if dfs(t1,t2):return True\n",
    "        else:return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def isSame(self, t1, t2):\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "            \n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        \n",
    "        if t1.val != t2.val:\n",
    "            return False\n",
    "\n",
    "        return self.isSame(t1.left, t2.left) and self.isSame(t1.right, t2.right)\n",
    "\n",
    "\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        \n",
    "        if t1.val == t2.val and self.isSame(t1, t2):\n",
    "            return True\n",
    "\n",
    "        return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t2 or not t1:return False\n",
    "        def dfs(t1,t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            elif not t1 or not t2:\n",
    "                return False\n",
    "            else:\n",
    "                if t1.val==t2.val:\n",
    "                    res = dfs(t1.left,t2.left) and dfs(t1.right,t2.right)\n",
    "                    if res:return True\n",
    "                return False\n",
    "        return dfs(t1,t2) or self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def checknode(node1, node2):\n",
    "            if node1 == None and node2 == None:\n",
    "                return True\n",
    "            if node1 == None or node2 == None:\n",
    "                return False\n",
    "            if node1.val != node2.val:\n",
    "                return False\n",
    "            if not checknode(node1.left, node2.left) or not checknode(node1.right, node2.right):\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        q = deque([t1])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if checknode(node, t2):\n",
    "                return True\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def dfs(t1, t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            if not t1 or not t2:\n",
    "                return False\n",
    "            return t1.val==t2.val and dfs(t1.left, t2.left) and dfs(t1.right, t2.right)\n",
    "\n",
    "        #都为空？\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        if dfs(t1, t2):\n",
    "            return True\n",
    "        return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def compareAB(self, A, B):\n",
    "        if not B and not A:\n",
    "            return True\n",
    "        if not A or not B or A.val != B.val:\n",
    "            return False\n",
    "        return self.compareAB(A.left, B.left) and self.compareAB(A.right, B.right)\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1:\n",
    "            return not t2\n",
    "        if not t2:\n",
    "            return True\n",
    "        if t1.val == t2.val and self.compareAB(t1,t2):\n",
    "            return True\n",
    "        return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def recur(A,B):\n",
    "            if not A and not B:\n",
    "                return True\n",
    "            if not A or not B:\n",
    "                return False\n",
    "            return  A.val==B.val and recur(A.left,B.left) and recur(A.right,B.right)\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        if recur(t1,t2):\n",
    "            return True\n",
    "        return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        \n",
    "        def check_all_equal(t1, t2):\n",
    "            if not t2 and not t1:\n",
    "                return True\n",
    "            if not t2 and t1:\n",
    "                return False\n",
    "            if not t1:\n",
    "                return False\n",
    "            if t1.val == t2.val:\n",
    "                return check_all_equal(t1.left, t2.left) and check_all_equal(t1.right, t2.right)\n",
    "\n",
    "        if not t2:\n",
    "            return True\n",
    "        if not t1:\n",
    "            return False\n",
    "        \n",
    "        if t1.val == t2.val:\n",
    "            if check_all_equal(t1, t2): return True\n",
    "\n",
    "        return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if t1 == None and t2 == None:\n",
    "            return True\n",
    "        elif t1 == None or t2 == None:\n",
    "            return False\n",
    "        return self.checkSameTree(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "    \n",
    "    def checkSameTree(self, t1, t2):\n",
    "        if t1 == None and t2 == None:\n",
    "            return True\n",
    "        elif t1 == None or t2 == None:\n",
    "            return False\n",
    "        else:\n",
    "            return t1.val == t2.val and self.checkSameTree(t1.left, t2.left) and self.checkSameTree(t1.right, t2.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_valid(self, p, q):\n",
    "        if not p and not q:\n",
    "            return True\n",
    "        if not p or not q:\n",
    "            return False\n",
    "        return p.val == q.val and self.is_valid(p.left, q.left) and self.is_valid(p.right, q.right)\n",
    "\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1:\n",
    "            return not t2\n",
    "        return self.is_valid(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.flag = False\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        self.dfs(t1, t2)\n",
    "        return self.flag\n",
    "        \n",
    "\n",
    "    def dfs(self, t1, t2):\n",
    "        \n",
    "        if t1 == None and t2 == None:\n",
    "            return True\n",
    "\n",
    "        if t1 == None or t2 == None:\n",
    "            return False\n",
    "\n",
    "        if t1.val == t2.val:\n",
    "            left = self.dfs(t1.left, t2.left)\n",
    "            right = self.dfs(t1.right, t2.right)\n",
    "            self.flag = left and right\n",
    "        \n",
    "        \n",
    "        self.dfs(t1.left, t2)\n",
    "        self.dfs(t1.right, t2)\n",
    "\n",
    "        return t1.val == t2.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1:\n",
    "            return False\n",
    "        if self.isMatched(t1, t2):\n",
    "            return True\n",
    "        return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "    \n",
    "    def isMatched(self, t1:TreeNode, t2:TreeNode) -> bool:\n",
    "        if t1 is None and t2 is None:\n",
    "            return True\n",
    "        if not t1 or not t2 or t1.val != t2.val:\n",
    "            return False\n",
    "        return self.isMatched(t1.left, t2.left) and self.isMatched(t1.right, t2.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def isSimilar(A: TreeNode, B: TreeNode)-> bool:\n",
    "            if A is None and B is None:\n",
    "                return True\n",
    "            elif A is None and B:\n",
    "                return False\n",
    "            elif A and B is None:\n",
    "                return False\n",
    "            else:\n",
    "                 if A.val==B.val:\n",
    "                     return isSimilar(A.left,B.left) and isSimilar(A.right,B.right)\n",
    "                 else:\n",
    "                     return False\n",
    "        if t1 is None:\n",
    "            return False\n",
    "        else:\n",
    "            if t2 is None:\n",
    "                return False\n",
    "            else:\n",
    "                if t1.val==t2.val:\n",
    "                    return isSimilar(t1,t2) or self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "                else:\n",
    "                    return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:\n",
    "        def is_equal(node_a, node_b):\n",
    "            if not node_a and not node_b:\n",
    "                return True\n",
    "\n",
    "            if not node_a or not node_b:\n",
    "                return False\n",
    "\n",
    "            return node_a.val == node_b.val and is_equal(node_a.left, node_b.left) and is_equal(node_a.right, node_b.right)\n",
    "\n",
    "        if is_equal(root, subRoot):\n",
    "            return True\n",
    "\n",
    "        if not root and subRoot:\n",
    "            return False\n",
    "\n",
    "        return self.checkSubTree(root.left, subRoot) or self.checkSubTree(root.right, subRoot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t2 or not t1:return False\n",
    "        def dfs(t1,t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            elif not t1 or not t2:\n",
    "                return False\n",
    "            else:\n",
    "                return t1.val==t2.val and dfs(t1.left,t2.left) and dfs(t1.right,t2.right)\n",
    "        return dfs(t1,t2) or self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        res = False\n",
    "\n",
    "        def check(node1, node2):\n",
    "            if not node1 and not node2:\n",
    "                return True\n",
    "            if not node1 or not node2:\n",
    "                return False\n",
    "            if node1.val == node2.val:\n",
    "                return check(node1.left, node2.left) and check(node1.right, node2.right)\n",
    "        \n",
    "\n",
    "        def preorder(node):\n",
    "            nonlocal res\n",
    "            if not node or res:\n",
    "                return \n",
    "            \n",
    "            if node.val == t2.val:\n",
    "                if check(node, t2):\n",
    "                    res = True\n",
    "            preorder(node.left)\n",
    "            preorder(node.right)\n",
    "            return \n",
    "        \n",
    "        preorder(t1)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.flag = False\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        self.dfs(t1, t2)\n",
    "        return self.flag\n",
    "        \n",
    "\n",
    "    def dfs(self, t1, t2):\n",
    "        \n",
    "        if t1 == None and t2 == None:\n",
    "            return True\n",
    "\n",
    "        if t1 == None or t2 == None:\n",
    "            return False\n",
    "\n",
    "        if t1.val == t2.val:\n",
    "            left = self.dfs(t1.left, t2.left)\n",
    "            right = self.dfs(t1.right, t2.right)\n",
    "            self.flag = left and right\n",
    "        \n",
    "        if self.flag == False:\n",
    "            self.dfs(t1.left, t2)\n",
    "            self.dfs(t1.right, t2)\n",
    "        else:\n",
    "            return True\n",
    "\n",
    "        return t1.val == t2.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t2 or not t1:return False\n",
    "        def dfs(t1,t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            elif not t1 or not t2:\n",
    "                return False\n",
    "            else:\n",
    "                return t1.val==t2.val and dfs(t1.left,t2.left) and dfs(t1.right,t2.right)\n",
    "        return dfs(t1,t2) or self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def dfs(t1,t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            if not t1 or not t2:\n",
    "                return False\n",
    "            return t1.val==t2.val and dfs(t1.left,t2.left) and dfs(t1.right,t2.right)\n",
    "\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        if dfs(t1,t2):\n",
    "            return True\n",
    "        return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1 and not t2: return True\n",
    "        if not t1 or not t2: return False\n",
    "\n",
    "        def dfs(node1, node2):\n",
    "            if not node1 and not node2: return True\n",
    "            if not node1 or not node2: return False\n",
    "\n",
    "            if node1.val != node2.val: return False\n",
    "\n",
    "            return dfs(node1.left, node2.left) and dfs(node1.right, node2.right)\n",
    "        \n",
    "        return dfs(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def dfs(root1,root2):\n",
    "            if not root1 and not root2:\n",
    "                return True\n",
    "            if not root1 or not root2:\n",
    "                return False\n",
    "            return root1.val == root2.val and dfs(root1.left,root2.left) and dfs(root1.right,root2.right)\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        if dfs(t1,t2):\n",
    "            return True\n",
    "        return self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def issame(self, t1, t2):\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        if t1.val != t2.val:\n",
    "            return False\n",
    "        return self.issame(t1.left, t2.left) and self.issame(t1.right, t2.right)\n",
    "\n",
    "\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        return self.issame(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def _tree_eq(self, t1, t2):\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "\n",
    "        val_eq = t1.val == t2.val\n",
    "        left_eq = self._tree_eq(t1.left, t2.left)\n",
    "        right_eq = self._tree_eq(t1.right, t2.right)\n",
    "\n",
    "        return val_eq and left_eq and right_eq\n",
    "    \n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1:\n",
    "            return False\n",
    "            \n",
    "        if not t2:\n",
    "            return True\n",
    "\n",
    "        if self._tree_eq(t1, t2):\n",
    "            return True\n",
    "        \n",
    "        leq = self.checkSubTree(t1.left, t2)\n",
    "        req = self.checkSubTree(t1.right, t2)\n",
    "\n",
    "        return leq or req\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2) or self.is_equal(t1, t2)\n",
    "    \n",
    "    def is_equal(self, t1, t2):\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        return t1.val == t2.val and self.is_equal(t1.left, t2.left) and self.is_equal(t1.right, t2.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def dfs(t1, t2):\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            if not t1 or not t2:\n",
    "                return False \n",
    "            return t1.val == t2.val and dfs(t1.left, t2.left) and dfs(t1.right, t2.right)\n",
    "\n",
    "        if not t1 and not t2:\n",
    "            return True\n",
    "        if not t1 or not t2:\n",
    "            return False\n",
    "        if dfs(t1, t2):\n",
    "            return True\n",
    "        return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        #寻找t1中t2的位置\n",
    "        #t1先越过叶子结点，返回t2的逻辑非\n",
    "        if not t1:\n",
    "            return not t2\n",
    "        #t2先越过叶子结点，返回true\n",
    "        if not t2:\n",
    "            return True\n",
    "        #返回向下递归的结果\n",
    "        return self.DFS(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "\n",
    "    def DFS(self, t1, t2):\n",
    "        if not t2 and not t1:\n",
    "            return True\n",
    "        elif not t2 or not t1:\n",
    "            return False \n",
    "        elif t1.val != t2.val:\n",
    "            return False\n",
    "        else:\n",
    "            return self.DFS(t1.left, t2.left) and self.DFS(t1.right, t2.right)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def issame(root1, root2):\n",
    "            if not root1 and not root2:\n",
    "                return True\n",
    "            elif not root1 or not root2:\n",
    "                return False\n",
    "            elif root1.val != root2.val:\n",
    "                return False\n",
    "            else:\n",
    "                return issame(root1.left, root2.left) and issame(root1.right, root2.right)\n",
    "\n",
    "        if not t2:\n",
    "            return True\n",
    "        elif not t1:\n",
    "            return False\n",
    "        else:\n",
    "            return issame(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if t1 == t2:\n",
    "            return True\n",
    "        \n",
    "        if not t1:\n",
    "            return False\n",
    "\n",
    "        def dfs(t1: TreeNode, t2: TreeNode) -> bool:\n",
    "            if not t1 and not t2:\n",
    "                return True\n",
    "            \n",
    "            if t1 and t2 and t1.val == t2.val:\n",
    "                return dfs(t1.left, t2.left) and dfs(t1.right, t2.right)\n",
    "            \n",
    "            return False\n",
    "        \n",
    "        return dfs(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        if t1 is None : return False\n",
    "        def help(tree1, tree2):\n",
    "            if tree1 is None and tree2 is None: return True\n",
    "            if tree1 is None or tree2 is None: return False\n",
    "            if tree1.val != tree2.val:return False\n",
    "            return help(tree1.left, tree2.left) and help(tree1.right, tree2.right)\n",
    "        print(help(t1,t2))\n",
    "        return True if help(t1, t2) else self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        stack=[t1]\n",
    "        while stack:\n",
    "            head=stack.pop(0)\n",
    "            if self.compare(head,t2):\n",
    "                return True\n",
    "            if head.right:\n",
    "                stack.append(head.right)\n",
    "            if head.left:\n",
    "                stack.append(head.left)\n",
    "        return False\n",
    "    \n",
    "    def compare(self,root,subRoot):\n",
    "        stackRoot=[root]\n",
    "        stackSubRoot=[subRoot]\n",
    "        while stackRoot or stackSubRoot:\n",
    "            try:\n",
    "                headRoot=stackRoot.pop(0)\n",
    "                headSubRoot=stackSubRoot.pop(0)\n",
    "            except IndexError:\n",
    "                return False\n",
    "            else:\n",
    "                if headRoot.val==headSubRoot.val:\n",
    "                    if headRoot.right:\n",
    "                        stackRoot.append(headRoot.right)\n",
    "                    if headRoot.left:\n",
    "                        stackRoot.append(headRoot.left)\n",
    "                    if headSubRoot.right:\n",
    "                        stackSubRoot.append(headSubRoot.right)\n",
    "                    if headSubRoot.left:\n",
    "                        stackSubRoot.append(headSubRoot.left)\n",
    "                    if ((headRoot.right==None)^(headSubRoot.right==None)) or ((headRoot.left==None)^(headSubRoot.left==None)):\n",
    "                        return False\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "    #     if not t1 and not t2:\n",
    "    #         return True\n",
    "    #     if not t1 or not t2:\n",
    "    #         return False\n",
    "        \n",
    "    #     return self.checksame(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)\n",
    "\n",
    "\n",
    "    # def checksame(self, t1, t2):\n",
    "    #     if not t1 and not t2:\n",
    "    #         return True\n",
    "    #     if not t1 or not t2:\n",
    "    #         return False\n",
    "            \n",
    "    #     return t1.val==t2.val and self.checksame(t1.left, t2.left) and self.checksame(t1.right, t2.right)\n",
    "        def dfs(x):\n",
    "            if not x:\n",
    "                return '#'\n",
    "            return 'v'+str(x.val)+dfs(x.left)+dfs(x.right)\n",
    "        print(dfs(t2), dfs(t1))\n",
    "        return dfs(t2) in dfs(t1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        q = queue.Queue()\n",
    "        q.put(t1)\n",
    "        def check(t1, t2):\n",
    "            if t1 is None and t2 is None:\n",
    "                return True\n",
    "            if t1 is None and not (t2 is None):\n",
    "                return False\n",
    "            if not (t1 is None) and t2 is None:\n",
    "                return False\n",
    "            if t1.val == t2.val:\n",
    "                if not t1.left and not t2.left and not t1.right and not t2.right:\n",
    "                    return True\n",
    "                return check(t1.left, t2.left) and check(t1.right, t2.right)\n",
    "            return False\n",
    "        while not q.empty():\n",
    "            t = q.get()\n",
    "            if t.val == t2.val:\n",
    "                flag = check(t, t2)\n",
    "                if flag:\n",
    "                    return flag\n",
    "            if t.left != None:\n",
    "                q.put(t.left)\n",
    "            if t.right != None:\n",
    "                q.put(t.right)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        def tree2str(node):\n",
    "            if node is None:\n",
    "                return ''\n",
    "            return '('+str(node.val)+\")\" + '[' + tree2str(node.left) + \"]\" + '[' + tree2str(node.right) + ']'\n",
    "        \n",
    "        str1 = tree2str(t1)\n",
    "        str2 = tree2str(t2)\n",
    "        #print(str1.find(str2))\n",
    "        return str1.find(str2) != -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
